public class DynamicPlanningPractise {
    /**
     * 打家劫舍Ⅰ*/
    public int robOther(int[] nums) {
        //状态表示：f[i]代表当以i位置为终点时，i位置必闯入，此时的最高金额
        //         g[i]代表当以i位置为终点时，i位置必不被闯入，此时的最高金额
        //状态转移方程： f[i] = g[i-1] + nums[i]；
        //              g[i] = Math.max(f[i-1],g[i-1]);
        //初始化：f[0] = nums[0];
        //       g[0] = 0

        int n = nums.length;
        //1 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //2 初始化
        f[0] = nums[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            //4 状态转移方程
            f[i] = g[i-1] + nums[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //5 返回值
        return Math.max(f[n-1],g[n-1]);
    }
    /**
     * 打家劫舍Ⅱ
     * */
    public int rob(int[] nums) {
        //分类讨论
        int n = nums.length;
        return Math.max(nums[0] + rob1(nums,2,n-2),rob1(nums,1,n-1));
    }
    public int rob1(int[] nums, int left, int right) {
        int n = right - left + 1;//实际大小
        if(n <= 0) return 0; //范围无效，返回0
        //1 创建dp表
        int[] f = new int[n];
        int[] g = new int[n];
        //2 初始化
        f[0] = nums[left];
        //3 填表
        for(int i = 1; i < n; i++) {
            //4 状态转移方程
            f[i] = g[i-1] + nums[left+i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        //5 返回值
        return Math.max(f[n-1],g[n-1]);
    }
    /**
     * 删除并获得点数*/
    public int deleteAndEarn(int[] nums) {
        /**
         将其转换为打家劫舍问题
         因为nums中可能存在重复的数组，并且数据之间并不连续，故为了解决这一问题，则需要对数据进行预处理
         创建一个最大的数组，将nums中的所有数据放入该数组中（以值为下标，元素为该值总和）
         创建一个大小为10001的数组--》数最大为10000*/

        //预处理
        int[] array = new int[10001];
        for(int i = 0; i < nums.length; i++)
            array[nums[i]] += nums[i];
        int n = array.length;
        //1 创建dp表
        int[] f = new int[10001];
        int[] g = new int[10001];
        //2 初始化
        f[0] = array[0];
        //3 填表
        for(int i = 1; i < n; i++) {
            f[i] = g[i-1] + array[i];
            g[i] = Math.max(f[i-1],g[i-1]);
        }
        return  Math.max(f[n-1],g[n-1]);
    }
}
